package java学习.代码随想录.动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/13 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 最后一块石头的重量II {

/**            0 1 2 3 4 5
 * 示例： 输入：[2,7,4,1,8,1] 输出：1
 * 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
 * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 *
 * 最后一块石头的重量 II
 * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
 *
 * 如果 x == y，那么两块石头都会被完全粉碎；
 * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最
 * 后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
 *
 *todo 要使最后一块石头的重量尽可能地小， 背包重量需要在不超过 {sum}/2 的前提下尽可能地大，尽量使背包容量尽可能接近sum/2,使得最后一个石头 sum-dp[]*2 最小
 *
 * 石头尽量分成 重量相仿的两堆，取较小的为 背包重量。
 * 若求出石头的总重量 sum ， 则最后一块重量 = sum - 2*dp[j]  23/2 = 11  sum-2*11=1.
 * bagsize= 大多都是总和/2
 * bagsize = sum/2
 * fori
 * for(j = sum/2  j>=w[i];j--)
 * dp[j] = dp[j]  dp[j-w[i]]+v[i]
 *
 */

    public static int lastStoneWeightII(int[] stones) {
        if(stones.length==0||stones==null){
            return 0;
        }
        int sum = 0;
        for (int stone : stones) {
            sum+=stone;
        }
        int bagsize  = sum/2;
        int []dp = new int[bagsize+1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = bagsize; j >=stones[i] ; j--) {
                dp[j] = Math.max(dp[j] , dp[j-stones[i]]+stones[i]);
            }
        }
//        dp[j]: 重量为j能背的最大石头的（重量） 01
        return sum-2*dp[bagsize];

    }
}
